package solution1.demo.demo6;


import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {

    //1.重排链表(II)
    private ListNode reverseList(ListNode head) {
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }


    public void reorderList(ListNode head) {
        if(head.next == null) {
            return ;
        }
        //分割链表
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        while(fast != null && fast.next != null) {
            prev = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        prev.next = null;
        //翻转后半段链表
        ListNode head2 = reverseList(slow);
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        //合并两个链表
        while(head != null && head2 != null) {
            cur.next = head;
            cur = cur.next;
            head = head.next;
            cur.next = head2;
            cur = cur.next;
            head2 = head2.next;
        }
        if(head != null) {
            cur.next = head;
        }
        if(head2 != null) {
            cur.next = head2;
        }
        head = dummy.next;
    }

    //2.用栈实现队列
    class MyQueue {

        private Stack<Integer> stack1;
        private Stack<Integer> stack2;

        public MyQueue() {
            this.stack1 = new Stack<>();
            this.stack2 = new Stack<>();
        }

        public void push(int x) {
            //先检测 stack2 中是否存在元素
            while(!stack2.isEmpty()) {
                stack1.push(stack2.pop());
            }
            stack1.push(x);
        }

        public int pop() {
            //先检测 stack1 中是否有数据，若有就将所有数据 pop 到 stack2
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }

        public int peek() {
            //先检测 stack1 中是否有数据，若有就将所有数据 pop 到 stack2
            while(!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

    //3.用队列实现栈
    class MyStack {

        private Queue<Integer> queue1;
        private Queue<Integer> queue2;

        public MyStack() {
            this.queue1 = new LinkedList<>();
            this.queue2 = new LinkedList<>();
        }

        public void push(int x) {
            queue1.offer(x);
        }

        public int pop() {
            //将 size - 1 个元素出队到 queue2
            int size = queue1.size();
            for(int i = 1; i < size; i++) {
                queue2.offer(queue1.poll());
            }
            int res = queue1.poll();
            //再将所有元素放回来
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }
            return res;
        }

        public int top() {
            //将 size - 1 个元素出队到 queue2
            int size = queue1.size();
            for(int i = 1; i < size; i++) {
                queue2.offer(queue1.poll());
            }
            int res = queue1.poll();
            queue2.offer(res);
            //再将所有元素放回来
            while(!queue2.isEmpty()) {
                queue1.offer(queue2.poll());
            }
            return res;
        }

        public boolean empty() {
            return queue1.isEmpty();
        }
    }

    //4.有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                //左括号入栈
                stack.push(ch);
            } else {
                //右括号进行匹配
                if(stack.isEmpty()) {
                    //这时为空一定是错误的
                    return false;
                }
                char topCh = stack.pop();
                if((topCh == '(' && ch != ')') || (topCh == '[' && ch != ']')
                        || (topCh == '{' && ch != '}')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    //5.删除字符串中的所有相邻重复项
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack();
        for(int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if(stack.isEmpty()) {
                stack.push(ch);
            } else {
                if(stack.peek() == ch) {
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
        }
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        return res.reverse().toString();
    }


    //6.逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            char ch = tokens[i].charAt(0);
            if((ch != '+' && ch != '-' && ch != '*' && ch != '/') ||
                    (tokens[i].length() != 1)) {
                //数字，入栈
                stack.push(Integer.parseInt(tokens[i]));
            } else {
                //运算符，取出栈中的两个数字进行运算(最先弹出来的是右数字)
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(ch) {
                    case '+':
                        stack.push(num1 + num2);
                        break;
                    case '-':
                        stack.push(num1 - num2);
                        break;
                    case '*':
                        stack.push(num1 * num2);
                        break;
                    case '/':
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    //7.验证栈序列(栈的压入弹出序列)
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;//弹出序列指针
        for(int i = 0; i < pushed.length; i++) {
            stack.push(pushed[i]);
            while(!stack.isEmpty() && popIndex < popped.length &&
                    popped[popIndex] == stack.peek()) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty() && popIndex == popped.length;
    }

    //8.滑动窗口的最大值(单调递减双端队列)
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(k == 1) {
            return nums;
        }
        int len = nums.length;
        int[] res = new int[len - k + 1];
        int index = 0;
        //维护一个单调递减双端队列
        Deque<Integer> deque = new LinkedList<>();
        deque.offerFirst(nums[0]);
        for(int i = 1; i < len; i++) {
            if(i < k - 1) {
                //维持递减队列
                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(nums[i]);
            } else {
                //维护递减队列
                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                    deque.pollLast();
                }
                deque.offerLast(nums[i]);
                res[index++] = deque.peekFirst();
                //如果要删除的元素是队列的第一个元素就删除
                if(deque.peekFirst() == nums[i - k + 1]) {
                    deque.pollFirst();
                }
            }
        }
        return res;
    }

//    //9.滑动窗口的最大值(妙)
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        if(k == 1) {
//            return nums;
//        }
//        int len = nums.length;
//        int[] res = new int[len - k + 1];
//        int index = 0;
//        Deque<Integer> deque = new LinkedList<>();
//        deque.offer(nums[0]);
//        for(int i = 1; i < len; i++) {
//            if(i < k - 1) {
//                //维护单调递减队列
//                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
//                    deque.pollLast();
//                }
//                deque.offerLast(nums[i]);
//            } else {
//                //维护单调递减队列
//                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
//                    deque.pollLast();
//                }
//                deque.offerLast(nums[i]);
//                res[index++] = deque.peekFirst();
//                //根据情况删除首元素
//                if(nums[i - k + 1] == deque.peekFirst()) {
//                    deque.pollFirst();
//                }
//
//            }
//        }
//        return res;
//    }

    //10.前 K 个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        //记录频率
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        //建立小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        int index = 0;
        for(int key : map.keySet()) {
            if(index < k) {
                queue.offer(key);
            } else {
                if(map.get(queue.peek()) < map.get(key)) {
                    queue.poll();
                    queue.offer(key);
                }
            }
            index++;
        }
        int[] res = new int[queue.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = queue.poll();
        }
        return res;
    }
}

class Main {

    public static void main(String[] args) {
        int[] arr = {1,3,1,2,0,5};
        Solution solution = new Solution();
        solution.maxSlidingWindow(arr, 3);
    }

}


